import java.util.ArrayList;
import java.util.List;

class Solution01 {
    // 回溯
    // 定义全局变量
    // 结果
    List<String> ret;
    // 路径
    StringBuffer path;
    // 左括号数量
    int left;
    // 右括号数量
    int right;
    int n;

    public List<String> generateParenthesis(int _n) {
        n = _n;
        ret = new ArrayList<>();
        path = new StringBuffer();
        dfs();
        return ret;
    }

    public void dfs() {
        // 结束条件
        if (right == n) {
            ret.add(path.toString());
            return;
        }
        // 添加左子树（左括号）
        if (left < n) {
            path.append('(');
            left++;
            dfs();
            // 回溯 -- 》 恢复现场
            path.deleteCharAt(path.length() - 1);
            left--;
        }
        if (right < left) {
            path.append(')');
            right++;
            dfs();
            // 回溯 -- 》 恢复现场
            path.deleteCharAt(path.length() - 1);
            right--;
        }
    }
}